
% Criado por P.J.de Rezende antes do Alvorecer da História.
% Modificado em 97-06-15 e 01-02-26 por J.Stolfi.
% modificado em 2003-06-07 21:12:18 por stolfi
% modificado em 2008-10-01 por cll
% \def\lastedit{2010-03-16 17:56:58 by stolfi}

\nonstopmode % PARA RODAR LATEX EM BATCH MODE
\documentclass[11pt,twoside]{article}

\usepackage{techrep-ic}

%%% SE USAR INGLÊS, TROQUE AS ATIVAÇÕES DOS DOIS COMANDOS A SEGUIR:
\usepackage[brazil]{babel}
%% \usepackage[english]{babel}

%%% SE USAR CODIFICAÇÃO LATIN1 OU UTF-8, ATIVE UM DOS DOIS COMANDOS A
%%% SEGUIR:
%%\usepackage[latin1]{inputenc}
\usepackage[utf8]{inputenc}

%%% Para obter o tamanho de texto recomendado:
\usepackage[margin=1in]{geometry}

%%% Para simbolos de math
\usepackage{amsmath,amssymb,amsfonts,latexsym}
\usepackage{listings}
\usepackage{graphicx}
\usepackage{subcaption}
\usepackage{color}
\usepackage{multirow}
\usepackage{url}

\definecolor{gray}{gray}{0.95}

\lstset{
  backgroundcolor=\color{gray},
  basicstyle=\ttfamily,
  breaklines=true,
  captionpos=b,
  columns=fixed,
  language=sh,
  showstringspaces=false,
  tabsize=2
}

\begin{document}

%%% PÁGINA DE CAPA %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Número do relatório
\TRNumber{02}

% DATA DE PUBLICAÇÃO (PARA A CAPA)
%
\TRYear{13} % Dois dígitos
\TRMonth{05} % Numérico, 01-12

% LISTA DE AUTORES PARA CAPA (sem afiliações).
\TRAuthor{R.A.Q. Cruz \and S.G. Fadel \and F.A. Neto}

% TÍTULO PARA A CAPA (use \\ para forçar quebras de linha).
\TRTitle{Um algoritmo distribuído para encontrar aleatoriamente um conjunto de
palavras}

\TRMakeCover

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% O que segue é apenas uma sugestão - sinta-se à vontade para
% usar seu formato predileto, desde que as margens tenham pelo
% menos 25mm nos quatro lados, e o tamanho do fonte seja pelo menos
% 11pt. Certifique-se também de que o título e lista de autores
% estão reproduzidos na íntegra na página 1, a primeira depois da
% página de capa.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Nomes de autores ABREVIADOS e titulo ABREVIADO,
% para cabeçalhos em cada página.
%
\markboth{Cruz, Fadel e Neto}{Um algoritmo distribuído para encontrar aleatoriamente um conjunto de
palavras}
\pagestyle{myheadings}
\thispagestyle{empty}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TÍTULO e NOMES DOS AUTORES, completos, para a página 1.
% Use "\\" para quebrar linhas, "\and" para separar autores.
%
\title{Um algoritmo distribuído para encontrar aleatoriamente um conjunto de
palavras}

\author{Rommel Anatoli Quintanilla Cruz \and Samuel Gomes Fadel \and Filipe
Alves Neto}

\date{}

\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{abstract}

Gerar um conjunto arbitrário de palavras de forma totalmente aleatória pode ser
uma tarefa difícil, porém esta tarefa é altamente paralelizável. Este trabalho é
parte da disciplina de Programação Concorrente do ICMC/USP com o objetivo de
avaliar uma solução paralela para esta tarefa. Concluiu-se que neste caso uma
boa abordagem de comunicação entre os processos é crucial para a eficiência da
solução.

\end{abstract}

\section{Introdução}

A computação paralela e distribuída é de grande utilidade quando o problema que
se quer resolver necessita de uma grande quantidade de processamento e quando os
algoritmos necessários são eficientemente paralelizáveis. Porém, a coordenação
das ferramentas que as diferentes abordagens nos forneceram não é uma tarefa
simples sobretudo quando se está a procura de desempenho ótimo.

Para o problema de encontrar de forma aleatória um conjunto de palavras
predeterminado, a condição de indeterminabilidade do algoritmo necessita do uso
extensivo das unidades de processamento, portanto o foco foi considerar um modo
conveniente de comunicação e sincronismo entre \emph{threads} e processos.

A implementação foi feita de forma híbrida e utilizou-se tanto a biblioteca de
memória distribuída MPI como a biblioteca de memória compartilhada OpenMP. Este
trabalho foi desenvolvido como parte do curso SC0143 -- Programação Concorrente
do Instituto de Ciências Matemáticas e de Computação (ICMC) da Universidade de
São Paulo (USP).

\section{Objetivos}

O objetivo deste trabalho é projetar, implementar e avaliar o desempenho de uma
solução para o problema de geração de um conjunto de palavras de forma
totalmente aleatória. A solução é capaz de atender aos seguintes requerimentos:

\begin{itemize}
    \item cada caractere de cada palavra foi gerado de forma totalmente
        aleatória;
    \item palavras com caracteres não alfabéticos foram descartadas;
    \item palavras com mais de cinco caracteres foram divididas em partes de, no
        máximo, cinco caracteres;
    \item portanto, foram geradas palavras com, no máximo, cinco caracteres;
    \item gerada uma palavra ou uma parte de palavra válida, esta foi
        marcada como encontrada e não foi aceita novamente;
    \item quando um processo encontrava uma palavra ou parte de palavra, os
        demais processos eram comunicados; e
    \item foram calculados os tempos para encontrar 10\%, 20\%, 30\%, 40\%,
        50\%, 60\%, 70\%, 80\%, 90\% e 100\% do total de palavras.
\end{itemize}

\section{Implementação}

O programa foi desenvolvido na linguagem de programação C utilizando a
implementação OpenMP do gcc\footnote{\url{http://gcc.gnu.org/wiki/openmp}} e a
biblioteca Open MPI\footnote{\url{http://www.open-mpi.org/}}.

O código fonte do programa está hospedado no repositório digital do Google Code
no endereço\\ \url{https://code.google.com/p/pc2013-grupo06-turmab/} na pasta
\texttt{t3}.

\subsection{Estrutura de dados}

Na solução implementada, buscou-se minimizar a comunicação entre os processos,
para que este não se tornasse o gargalo da solução. Para isso, primeiro é
construída uma árvore AVL para armazenar quais palavras estão sendo buscadas.
Entretanto, para acelerar a busca e para satisfazer o requirimento de um
processo poder encontrar somente até 5 letras de uma palavra, os nós da árvore
são compostos por palavras de, no máximo, 5 letras. Assim, cada processo pode
simplesmente gerar aleatoriamente uma palavra de até 5 letras e então buscá-la
na árvore, sem haver a necessidade de coordenar esta divisão entre vários
processos.

Para informar aos outros processos que uma palavra foi encontrada, ao invés de
informar qual palavra (ou parte de palavra) foi encontrada, um processo envia a
todos os outros um número, que representa um nó da árvore. Este número é obtido
após a construção árvore, percorrendo a ávore em ordem e então colocando um
ponteiro para cada nó num vetor, além de salvar o índice onde o nó foi salvo no
vetor no próprio nó. Desta forma, quando um processo recebe um inteiro de outro,
basta indexar o vetor com o inteiro, obtendo diretamente o nó da palavra (ou
parte de palavra) e removendo-o. A estrutura final está representada na
Figura~\ref{fig:Dicionario}, onde se mostra o caso em que as palavras sendo
buscadas são \texttt{brutelike}, \texttt{cave} e \texttt{brute}.

\begin{figure}[h]
    \centering
    \includegraphics[width=0.4\linewidth]{img/dictionary.eps}
    \caption{Esquematização da estrutura de dados adotada para otimizar a busca
    das palavras pré-definidas ao mesmo tempo que diminui a carga de comunicação
    entre os nós. Neste exemplo, as palavras usadas para construir a árvore são:
    \texttt{brutelike}, \texttt{cave} e \texttt{brute}.}
    \label{fig:Dicionario}
\end{figure}

Esta estrutura, porém, não é suficiente para determinar a porcentagem de
palavras que já foram encontradas, pois não há informação suficiente sobre a
composição original das palavras. Para isso, um nó é designado para ser o
\emph{root} e nele é usada uma outra estrutura, além da estrutura já descrita.
Nesta outra, há a associação entre as palavras originais e suas partes
espalhadas pela árvore. Na Figura~\ref{fig:DicionarioRoot}, está esquematizada a
estrutura para as palavras \texttt{brutelike}, \texttt{cave} e \texttt{brute}.
Para cada nó na árvore, existe uma lista encadeada que armazena em que posições
no vetor das palavras aquele pedaço ocorre. Por exemplo, no caso do nó
\texttt{brute}, estão armazenadas as posições \texttt{1} e \texttt{3} porque
este nó compõe tanto a palavra \texttt{brutelike} quanto a palavra
\texttt{brute}. No vetor, é armazenada a quantidade de nós que compõem a
palavra.

\begin{figure}[h]
    \centering
    \includegraphics[width=0.7\linewidth]{img/rdictionary.eps}
    \caption{Estrutura utilizada para armazenar informações sobre a composição
    original das palavras, usada para determinar a porcentagem de palavras
    encontradas. Neste exemplo, as palavras sendo buscadas são
    \texttt{brutelike}, \texttt{cave} e \texttt{brute}.}
    \label{fig:DicionarioRoot}
\end{figure}

Desta forma, toda vez que uma palavra (na árvore) é encontrada pelos outros
processos, quando o processo \emph{root} é informado, ele utiliza o número
recebido para encontrar o nó da palavra, conforme os outros processos, e então
passa a decrementar o valor de cada posição no vetor que estiver na lista
encadeada do nó.

\subsection{Decomposição do problema}
Com as estruturas de dados definidas, paralelizar o problema ficou mais simples,
pois o trabalho pode ser dividido igualmente entre todos os processos, com
exceção do processo \emph{root}. Para isso, cada processo ficou responsável por
gerar a palavra aleatória e então utilizar a árvore com as palavras para
verificar se a palavra gerada está sendo procurada.

Como esta tarefa não depende de outras, pode ser feita paralelamente tanto a
nível de memória distribuída quanto a nível de memória compartilhada entre
\emph{threads}. Cada processo possui uma \emph{thread} reservada para receber
informações dos outros nós sobre palavras encontradas enquanto as outras geram e
buscam palavras, enviando mensagens aos outros processos toda vez que uma
palavra for encontrada. Além disso, cada \emph{thread} em cada processo possui
uma semente única de geração de números aleatórios, evitando que haja repetição
nas geração das palavras.

\section{Resultados}

Nesta seção são apresentados os resultados de desempenho da solução proposta na
seção anterior. Na Figura~\ref{fig:Tempos} pode-se ver que a alta paralelização
da solução permitiu que o tempo de execução fosse reduzido com o acréscimo de
processos trabalhando ao mesmo tempo. Entretanto, houveram problemas com a
leitura do arquivo. Conforme pode ser visto na Figura~\ref{fig:TemposLeitura}, o
tempo de leitura oscilou e cresceu com o aumento do número de processos.
Acredita-se que isso se deve à forma de acesso ao disco durante a execução de
vários processos simultâneos, já que a função \texttt{MPI\_File\_open} e suas
correlatas são coletivas. Este fato prejudicou o tempo final de execução, mas a
solução proposta funcionou como previsto.

\begin{figure}[h]
    \centering
    \begin{subfigure}{0.7\textwidth}
        \centering
        \includegraphics[width=\linewidth]{img/tempos.eps}
        \caption{Tempos de execução, mostrados a cada 10\% de palavras
        encontradas, a partir de 0\%.}
        \label{fig:Tempos}
    \end{subfigure}
    \begin{subfigure}{0.5\textwidth}
        \centering
        \includegraphics[width=\linewidth]{img/tempos_leitura.eps}
        \caption{Tempos de leitura para cada quantidade de processos.}
        \label{fig:TemposLeitura}
    \end{subfigure}
\end{figure}

\section{Conclusões}

A solução proposta obteve ótimos resultados para o problema. A capacidade de
utilizar todos os recursos computacionais disponíveis, foi um dos principais
fatores para atingir bons resultados. Além disso, garantiu-se que cada
\emph{thread} responsável pela geração de palavras tivesse uma semente aleatória
diferente, reduzindo o número de palavras geradas repetidamente.

A escolha das estruturas de dados também foram fundamentais, destacando-se o uso
de árvores AVL com os nós indexados. O uso de índices nos nós da árvore reduziu
drasticamente a sobrecarga de comunicação entre os processos, uma vez que passou
a ser possível a transmissão apenas do índice das partes de palavra encontradas
e não todos os caracteres gerados.

O implementação de uma thread exclusiva para o recebimento das palavras
encontradas por outros processos foi uma decisão de projeto de impacto no
desempenho do programa, pois manteve todos os processos sincronizados, evitando
envios de partes repetidas. Ainda neste aspecto, a limitação da Open MPI de não
permitir envio e recebimento simultâneos de mensagens geraram um problema na
coordenação destas operações, no entanto, esse problema foi tratado utilizando a
diretiva de trecho de código crítico da OpenMP.

Como última consideração às decisões de projeto, manter as palavras completas
apenas sob o conhecimento do processo \texttt{root} permitiu diminuir a
complexidade dos demais processos sem prejudicar o funcionamento geral do
programa, inclusive melhorando a eficiência da solução.

Quanto ao tempo de execução total do programa, pode-se observar que este foi
apenas afetado pelo problema de leitura do arquivo, já que considerando apenas o
tempo de gerar e buscar as palavras diminuiu com o número de processos.
Portanto, a solução proposta para encontrar o conjunto de palavras
aleatoriamente é altamente paralelizável, necessitando apenas de uma forma
diferente de leitura do arquivo de entrada.

% TODO: falar da limitação do número mínimo de threads e processos

\bibliographystyle{abnt}
\bibliography{relatorio}

\end{document}
